class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, bool> mp;
        for (auto str : wordDict) mp[str] = true;
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int j = 0; j <= s.size(); j++) { //遍历“背包”
            for (int i = 0; i < j; i++) { //遍历“物品”
                if (dp[i] == false) continue;
                string word = s.substr(i, j - i);
                if (mp[word] == true) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.size()];
    }
};
